public class Leetcode {
}

//leetcode:322:零钱兑换
class Solution1 {
    public int coinChange(int[] coins, int amount) {
        int n = coins.length , INF = 0x3f3f3f3f;
        //创建一个dp表，表前i个硬币能凑成j的最小个数
        int[][] dp = new int[n+1][amount+1];

        for(int j = 1; j <= amount; j++) dp[0][j] = INF;
        for(int i = 1; i <= n; i++){
            for(int j = 0; j <= amount; j++){
                //不选第i个硬币
                dp[i][j] = dp[i-1][j];
                //选第i个硬币，但同时我们要判断选了第i个硬币后j的值要大于等于0，因为我们要在前i个位置(因为我们可以选重复的位置)去找能够凑成j-coins[i-1]的最小元素个数
                if(j >= coins[i-1])
                    //得到不选i位置硬币的个数和选i位置硬币个数的最小值
                    dp[i][j] = Math.min(dp[i][j] , dp[i][j - coins[i-1]] + 1);
            }
        }
        return dp[n][amount] == INF ? -1 : dp[n][amount];
    }
}

//滚动数组优化
class Solution2 {
    public int coinChange(int[] coins, int amount) {
        int n = coins.length , INF = 0x3f3f3f3f;
        int[] dp = new int[amount+1];

        for(int j = 1; j <= amount; j++) dp[j] = INF;
        for(int i = 1; i <= n; i++){
            for(int j = 0; j <= amount; j++){
                if(j >= coins[i-1])
                    dp[j] = Math.min(dp[j] , dp[j - coins[i-1]] + 1);
            }
        }
        return dp[amount] == INF ? -1 : dp[amount];
    }
}

//leetcode:518:零钱兑换II
class Solution3 {
    public int change(int amount, int[] coins) {
        int n = coins.length;
        //创建一个dp表，表示前i个硬币可以凑成j的组合个数
        int[][] dp = new int[n+1][amount+1];
        //前0个元素凑成0只有一种
        dp[0][0] = 1;
        for(int i = 1; i <= n; i++){
            for(int j = 0; j <= amount; j++){
                //不选i位置元素
                dp[i][j] = dp[i-1][j];
                //选第i个硬币，但同时我们要判断选了第i个硬币后j的值要大于等于0，因为我们要在前i个位置(因为我们可以选重复的位置)去找能够凑成j-coins[i-1]的组合个数
                if(j >= coins[i-1])
                    //将选和不选的个数加到一起就是总的组合个数
                    dp[i][j] +=  dp[i][j-coins[i-1]];
            }
        }
        return dp[n][amount];
    }
}

//滚动数组优化
class Solution4 {
    public int change(int amount, int[] coins) {
        int n = coins.length;
        int[] dp = new int[amount+1];

        dp[0] = 1;
        for(int i = 1; i <= n; i++){
            for(int j = 0; j <= amount; j++){
                if(j >= coins[i-1])
                    dp[j] +=  dp[j-coins[i-1]];
            }
        }
        return dp[amount];
    }
}